/*
 * shift.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#include "BigInt.h"
#include <sstream>
using namespace std;
using namespace APIAL;

void APIAL::LeftShift(BigInt *left, int shift_amt, BigInt *result)
{
	bool alias = false;

	// Check if alias
	if (left == result)
	{
		alias = true;
	}

	if (0 == shift_amt || 0 == left->size)
	{
		if (alias)
		{
			return;
		}
		else
		{
			*result = *left;
		}
	}

	// normalize
	BigInt::normalize(*left);

	// number of new chunks we will have to add as a result of the shift
	int chunks_to_add = shift_amt / left->nonCarryBits;

	// number of bits to shift within a chunk
	int bits_to_shift = shift_amt % left->nonCarryBits;

	// number of bits to shift in the opposite direction within a chunk
	int bits_to_shift_opp = left->nonCarryBits - bits_to_shift;

	// mask to keep least significant bits
	BigInt::chunkType mask_LS = left->nonCarryBitsMask >> bits_to_shift_opp;

	// determine required size of result
	int required_size = left->size + chunks_to_add + 1;

	// set alias
	BigInt::chunkType* answer;
	if (alias)
	{
		/*
			TODO: this function should accept a scratchSpace parameter like
			add does in order to not constantly allocate memory for aliasing.
			This will kill the performance of add, for example.
		*/
		answer = new BigInt::chunkType[required_size];
	}
	else
	{
		result->resize(required_size,false);
		answer = result->chunks;
	}

	memset(answer,0,chunks_to_add*sizeof(BigInt::chunkType));

	// special case for first chunk
	answer[chunks_to_add] = left->nonCarryBitsMask & (left->chunks[0] << bits_to_shift);

	// general case for middle chunks
	#pragma omp parallel for
	for (int left_i = 0; left_i < left->size-1; left_i++)
	{
		int answer_i = left_i + chunks_to_add + 1;
		BigInt::chunkType temp = left->chunks[left_i] >> bits_to_shift_opp;
		temp |= (left->chunks[left_i+1] << bits_to_shift) & left->nonCarryBitsMask;
		answer[answer_i] = temp;
	}

	// special case for last 
	answer[required_size-1] = (left->chunks[left->size-1] >> bits_to_shift_opp) & mask_LS;

	// if alias, set result
	if (alias)
	{
		delete[] result->chunks;
		result->chunks = answer;
		result->capacity = required_size;
	}

	result->size = required_size;
	while(result->size > 0 && 0 == result->chunks[result->size - 1])
	{
		result->size--;
	}
}

void APIAL::RightShift(BigInt *left, int shift_amt, BigInt *result)
{
	bool alias = false;

	// Check if alias
	if (left == result)
	{
		alias = true;
	}

	if (0 == shift_amt || 0 == left->size)
	{
		if (alias)
		{
			return;
		}
		else
		{
			*result = *left;
		}
	}

	// normalize
	BigInt::normalize(*left);

	// number of new chunks we will have to add as a result of the shift
	int chunks_to_remove = shift_amt / left->nonCarryBits;

	// number of bits to shift within a chunk
	int bits_to_shift = shift_amt % left->nonCarryBits;

	// number of bits to shift in the opposite direction within a chunk
	int bits_to_shift_opp = left->nonCarryBits - bits_to_shift;

	// mask to keep least significant bits
	BigInt::chunkType mask_LS = left->nonCarryBitsMask >> bits_to_shift;

	// determine required size of result
	int required_size = left->size - chunks_to_remove;

	// check if we don't have to perform a shift
	if (required_size <= 0)
	{
		result->size = 0;
	}
	else // must perform shift
	{
		// set alias
		BigInt::chunkType* answer;
		if (alias)
		{
			answer = new BigInt::chunkType[required_size];
		}
		else
		{
			result->resize(required_size,false);
			answer = result->chunks;
		}

		// general case for middle chunks
		#pragma omp parallel for
		for (int left_i = chunks_to_remove; left_i < left->size; left_i++)
		{
			int answer_i = left_i - chunks_to_remove;
			BigInt::chunkType temp = left->chunks[left_i] >> bits_to_shift;
			temp |= (left->chunks[left_i+1] << bits_to_shift_opp) & left->nonCarryBitsMask;
			answer[answer_i] = temp;
		}

		// special case for last chunk
		answer[required_size-1] = (left->chunks[left->size-1] >> bits_to_shift) & mask_LS;

		// if alias, set result
		if (alias)
		{
			delete[] result->chunks;
			result->chunks = answer;
			result->capacity = required_size;
		}

		result->size = required_size;
		while(result->size > 0 && 0 == result->chunks[result->size - 1])
		{
			result->size--;
		}
	}
}

